perm filename CRE.DOC[CRE,BGB]1 blob
sn#021796 filedate 1973-01-25 generic text, type T, neo UTF8
00100 SAILON NUMBER 71. DRAFT CRE MANUAL.
00200
00300
00400 STANFORD ARTIFICIAL INTELLIGENCE LABORATORY JANUARY 1973.
00500 OPERATING NOTE NUMBER 71.
00600
00700
00800
00900 - - - DRAFT - - -
01000 Contour-Region-Edge Image Representation.
01100
01200
01300 Bruce g. Baumgart
01400
01500
01600 ABSTRACT:
01700
01800 A contour-region-edge, CRE, image representation is stated
01900 and an algorithm for converting a digital television image into this
02000 format is explained. An implementation of the algorithm is the main
02100 routine of a program called Cart's Eye, CRE; auxiliary routines
02200 provide manual cart control, TV camera input, image display, and
02300 Xerox Graphics Printer output. Potential application of CRE as a step
02400 in object perception is discussed.
02500
02600
02610 ATTENTION: The Very Latest CRE manual is obtained
02620 by listing files named 1,2,3,4,5 from [CRE,BGB].
02630
02700 CONTENTS:
02800
02900 I.
03000 A. DATA STRUCTURE.
03100 B. THE ALGORITHM.
03200 C. PERFORMANCE.
03300 II.
03400 A. TELETYPE COMMANDS.
03500 B. FILE FORMATS.
03600 C. SAIL INTERFACING.
03700 D. LISP INTERFACING.
03800 III.
03900 A. EDITORIAL REMARKS.
04000 B. CODE DOCUMENTATION.
04100 C. APPENDICES.
04200
04300
04400 This research was supported by the Advanced Research Projects Agency
04500 of the Office of the Secretary of Defense under contract SD-183.
00100 INTRODUCTION.
00200
00300
00400 CRE is a solution to the problem of finding all the
00500 photometric edges in a television picture and the regions bounded by
00600 those edges; this is done by building the edges and regions on top of
00700 a very literal intensity contour map. Edges are formed where contour
00800 lines run close together and regions are closed by following contour
00900 lines across the "flatlands" until they return to their edges. CRE
01000 also solves the small angle correspondence problem by linking the
01100 edges of one image with those of the next; this is done in a straight
01200 forward manner using a very large array.
01300
01400 The process is automatic and is intended to run without human
01500 intervention. Furthermore, the process is "bottom up"; there are no
01600 significant inputs other than the given television images. The CRE
01700 design goal is to provide video image input data in a basic list
01800 structured form appropriate for my geometric editor, GEOMED; other
01900 aspects of the vision problem such as 3D perception, object
02000 recognition, wide angle comparison, photometric normalization, and so
02100 on are not attempted in CRE.
00100 I. A. DATA STRUCTURE.
00200
00300
00400 Contour-Region-Edge or CRE, is a combination of ideas; the
00500 two principle idea being that of an elevation contour map and that of
00600 a political map. On a contour map of a continent fully surrounded by
00700 ocean, no two contour lines every cross and all the contour lines
00800 close. Consequently, the loops of elevation contours enclose
00900 regions; and these regions overlap in a nested fashion forming a tree
01000 data structure. On political maps, ignoring for the moment geographic
01100 pathologies such as Vietnam and the Vatican; no two states ever
01200 overlap, the states are bounded by borders, and the regions within
01300 the borders are simply connected.
01400
01500 One principle idea that is emphatically not in CRE is that of
01600 a schematic line drawing. Although the CRE output can be viewed as a
01700 collection of lines on a display screen, people expecting a line
01800 drawing rendition of the given television picture will be
01900 disappointed. A CRE picture is a simple translation of the
02000 photometry, geometry and topology of the orginal video image. Whereas
02100 the typical line drawing from a human illustrator is a representation
02200 of the scene without photometric information.
02300
02400 The data structure to be discussed is implemented as small
02500 blocks of words containing pointers and data in the fashion usual to
02600 graphics and simulation; an introduction to this technology can be
02700 found in Knuth [1]. The language of implementation is PDP-10 machine
02800 code via the FAIL assembler. The direct explanation of CRE structure
02900 will be presented in three parts: first, the several kinds of nodes
03000 will be briefly explained; second, the sub-structures such as rings,
03100 trees and lists will be discribed; and third, the detailed node
03200 formats will be given.
00100 TYPES OF NODES.
00200
00300 The are several types of CRE nodes: Vector-Arc-Vertex,
00400 Polygon, Face, Edge, Image, Level, Film, Empty and General. At the
00500 very top of all the structure is the film node, the film node is
00600 unique and serves as an OBLIST from which all other nodes may be
00700 reached. The film node represents the idea of a piece of celluloid
00800 film or a length of magnetic video tape; namely a film is a sequence
00900 of images taken by the same camera of the same scene with only a
01000 small amount of action or difference between images.
01100
01200 An image node represents the famialiar two dimensional idea
01300 of a photograph or an oil painting. An image node has two immediate
01400 sub structures that may exist simultaneously; there is the intensity
01500 contour image composed of level and polygon nodes, and there is the
01600 winged edge image composed of faces and edges.
01700
01800 The level node represents a photometrically binary image that
01900 results from thresholding a gray scale image.
02000
02100
02200 A CRUDE DIAGRAM OF NODE "IMMEDIACY" BY TYPE.
02300
02400 FILM →→→ Empties
02500 ↓
02600 ↓
02700 ↓
02800 ←←←←←← IMAGES →→→→→→→
02900 ↓ ↓
03000 ↓ ↓
03100 ↓ ↓
03200 FACES & EDGES LEVELS & POLYGONS
03300 ↓ ↓
03400 ↓ ↓
03500 ↓ ↓
03600 VECTORS, ARCS & VERTICES
00100 CRE SUB-STRUCTURES:
00200
00300 SEVEN RINGS.
00400 1. Image Ring of a Film.
00500 2. Level Ring of an Image.
00600 3. Polygon Ring of a Level.
00700 4. Vector Ring of a Polygon.
00800 5. Arc Ring of a Polygon.
00900 *6. Face Ring of an Image.
01000 *7. Edge Ring of an Image.
01100
01200 THREE PAIRS.
01300 1. Arc↔Vector Pairs.
01400 2. Vector↔Vector Radial Pairs.
01500 3. Arc↔Arc Radial Pairs.
01600
01700 TWO TREES.
01800 1. The Tree of Rings.
01900 2. The Polygon Tree.
02000
02100 TWO LISTS.
02200 1. Time Lists.
02300 2. The empty node list.
02400
02500 ONE EULER GRAPH.
02600 1. WINGED EDGE STRUCTURE - Face, Edge, Vertex.
00100 VECTOR/ARC/VERTEX NODE FORMAT.
00200
00300 _____________________________________________
00400 word | CW | CCW |
00500 0 | vector ring |
00600 _____|___________________|___________________|
00700 word | ROW | COL |
00800 1 | ∂ 0000.00 | ∂ 0000.00 |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | ∂ 1 | ∂ 303 313 |
01200 _____|___________________|___________________|
01300 word | | |
01400 3 | ENDO | EXO |
01500 _____|___________________|___________________|
01600 word | | |
01700 4 | ARC | PED |
01800 _____|___________________|___________________|
01900 word | | |
02000 5 | ∂ CNTRST | PGON |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 POLYGON NODE FORMAT.
02800
02900 _____________________________________________
03000 word | CW | CCW |
03100 0 | polygon ring |
03200 _____|___________________|___________________|
03300 word | DAD | SON |
03400 1 | level | 1st vector |
03500 _____|___________________|___________________|
03600 word | TYPE | RELOC |
03700 2 | 10 | 333 233 |
03800 _____|___________________|___________________|
03900 word | | |
04000 3 | ENDO | EXO |
04100 _____|___________________|___________________|
04200 word | | |
04300 4 | ARC | NCNT |
04400 _____|___________________|___________________|
04500 word | | |
04600 5 | NGON | PGON |
04700 _____|___________________|___________________|
04800 word | | |
04900 6 | NTIME | PTIME |
05000 _____|___________________|___________________|
00100 THE VECTOR/ARC/VERTEX NODE.
00200
00300 The most numerous kind of node is the VECTOR/ARC/VERTEX,
00400 which for informal discussion will be called a VERTEX.
00500
00600 Vertices carry the fundamental geometric datum of an image locus. The
00700 image locus is stored in halfword positions named ROW and COL, which
00800 contain the row and column of a point in units 1/64 of a pixel. A
00900 "pixel" is a "picture element".
01000
01100 Vertices when used as vectors or arcs also carry the fundamental
01200 photometric datum of edge contrast. Fundamental data is that data
01300 which comes almost irectly from the video image and is used to
01400 compute other data such face area or region gradient.
01500
01600 Vertices always belong to a polygon node, a pointer to the polygon of
01700 each vertex is stored in the link named PGON; as members of a polygon
01800 the vertices form a perimeter or loop which is always connected so
01900 that each vertex has a neighboring vertex in the clockwise and in the
02000 counter clockwise directions about the polygon's perimeter. There
02100 perimeter pointers re stored in the link positions named CW and CCW.
02200
02300 The links named NTIME and PTIME appear in all nodes except
02400 the film node; these links connect corresponding parts of a given
02500 image with parts of its immediate predecessor image and with parts of
02600 its immediate successor image. Time links implement the notion of a
02700 film where each frame differs but little from its neighboring frames
02800 along the film.
00100 THE EDGE NODE FORMAT.
00200
00300 _____________________________________________
00400 word | NCW clockwise NCW |
00500 0 | wings |
00600 _____|___________________|___________________|
00700 word | NCCW counter PCCW |
00800 1 | clockwise wings |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | ∂ 02 | ∂ 400 000 |
01200 _____|___________________|___________________|
01300 word | | |
01400 3 | NFACE | PFACE |
01500 _____|___________________|___________________|
01600 word | edge-ring |
01700 4 | NED | PED |
01800 _____|___________________|___________________|
01900 word | | |
02000 5 | NVT | PVT |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 WINGED EDGE MANDALA:
02800
02900 \ /
03000 nccw \ / pcw
03100 \ /
03200 ⊗ pvt
03300 |
03400 nface E pface
03500 |
03600 nvt ⊗
03700 / \
03800 ncw / \ pccw
03900 / \
00100 FACE NODE FORMAT.
00200
00300 _____________________________________________
00400 word | CW | CCW |
00500 0 | vector ring |
00600 _____|___________________|___________________|
00700 word | DAD | |
00800 1 | image | |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | ∂ 04 | ∂ 023 103 |
01200 _____|___________________|___________________|
01300 word | face-ring |
01400 3 | NFACE | PFACE |
01500 _____|___________________|___________________|
01600 word | | |
01700 4 | | PED |
01800 _____|___________________|___________________|
01900 word | | |
02000 5 | ∂ PERIM | ∂ AREA |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 FILM NODE FORMAT.
02800
02900 _____________________________________________
03000 word | | |
03100 0 | | core size |
03200 _____|___________________|___________________|
03300 word | | SON |
03400 1 | | image |
03500 _____|___________________|___________________|
03600 word | TYPE | RELOC |
03700 2 | ∂ 100 | 011 000 |
03800 _____|___________________|___________________|
03900 word | | |
04000 3 | | |
04100 _____|___________________|___________________|
04200 word | | |
04300 4 | | |
04400 _____|___________________|___________________|
04500 word | | |
04600 5 | | |
04700 _____|___________________|___________________|
04800 word | | |
04900 6 | | |
05000 _____|___________________|___________________|
00100 IMAGE NODE FORMAT.
00200
00300 _____________________________________________
00400 word | CW | CCW |
00500 0 | image ring |
00600 _____|___________________|___________________|
00700 word | DAD | SON |
00800 1 | film | level |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | 40 | 333 333 |
01200 _____|___________________|___________________|
01300 word | face ring |
01400 3 | NFACE | PFACE |
01500 _____|___________________|___________________|
01600 word | edge ring |
01700 4 | NED | PED |
01800 _____|___________________|___________________|
01900 word | vertex ring |
02000 5 | NVT | PVT |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 LEVEL NODE FORMAT.
02800
02900 _____________________________________________
03000 word | CW | CCW |
03100 0 | level ring |
03200 _____|___________________|___________________|
03300 word | DAD | SON |
03400 1 | image | polygon |
03500 _____|___________________|___________________|
03600 word | TYPE | RELOC |
03700 2 | ∂ 20 | ∂ 330 003 |
03800 _____|___________________|___________________|
03900 word | | |
04000 3 | | |
04100 _____|___________________|___________________|
04200 word | | |
04300 4 | | |
04400 _____|___________________|___________________|
04500 word | | |
04600 5 | | |
04700 _____|___________________|___________________|
04800 word | | |
04900 6 | NTIME | PTIME |
05000 _____|___________________|___________________|
00100 THE ALGORITHM.
00200
00300 In the large, CRE consists of five steps: thresholding,
00400 contouring, smoothing, bundling and comparing. The first four steps
00500 perform conversions between five kinds of images: 6-bit raster
00600 image, 1-bit raster image, vector intensity contour image, arc
00700 contour image, and winged edge image. The final step, comparing,
00800 joins an image to a film of images by linking the parts of the
00900 cuurent image to the parts of the previous image that compare nearly
01000 equal.
01100
01200 MAJOR OPERATION. OPERAND. RESULT.
01300
01400 1. THRESHOLDING: 6-BIT-IMAGE 1-BIT-IMAGES.
01500 2. CONTOURING: 1-BIT-IMAGES VIC-IMAGE.
01600 3. SMOOTHING: VIC-IMAGE ARC-IMAGE.
01700 4. BUNDLING: ARC-IMAGE WINGED-IMAGE.
01800 5. COMPARING: IMAGE & FILM FILM.
01900
00100 THRESHOLDING.
00200
00300 Thresholding, the first and easiest step, consists of two subroutines:
00400
00500 1. THRESH: CUT,TVBUF → PAC
00600 2. PACXOR: PAC → HSEG,VSEG
00700
00800 The subroutine THRESH takes an integer argument, 0 < CUT ≤ 63, and
00900 for each pixel in the TVBUF with value equal to or greater than the
01000 cut THRESH sets a bit in PAC. PAC (picture accumulator) is a bit
01100 array of 216 rows by 288 columns which takes 1728 words in the TVSEG.
01200
01300 The subroutine PACXOR first copies the PAC into two slightly larger
01400 bit arrays named HSEG and VSEG, then it exclusive OR's the PAC,
01500 properly displaced one row or one column, into HSEG and VSEG to
01600 compute the horizontal and vertical border bits of blobs in the PAC.
01700
01800
00100 CONTOURING.
00200
00300 Contouring, the next major step, converts the bit arrays HSEG
00400 and VSEG into a node-link data structure that represents an equal
00500 intensity level contour map. Of such contouring, there be two minor
00600 steps: one, that of tracing the contour as a ring of vectors to form
00700 a polygon; and two, that of placing the polygon in the contour tree
00800 data structure.
00900
01000 Although the notion of a contour
01100 map is familiar to everyone as a piece of paper from the Geodetic
01200 Survey Office; implementing the notion into a data structure becomes
01300 a magical mystery tour. Two of the contouring mysteries to be
01400 discussed are jaggies and nesting. The jaggies problem involves doing
01500 something to a rectilinear quantized set of segments, to make its
01600 linear nature more evident. The jaggies solution in CRE is called
01700 the dekinking, and merely involves vernier positioning the
01800 right-turns as will be explained below.
01900
02000 A JAGGY ILLUSTRATED.
02100
02200 ___
02300 |___
02400 |____
02500 |___
02600 |___
02700
02800 The nesting problem involves comparing two polygons and deciding
02900 whether one is within the other; although easy in an isolated case,
03000 solving alot of nesting becomes very expensive in compute time or in
03100 memory space. The nesting solution in CRE is a fast big memory one
03200 involving a 62K array, called the SKYSEG.
03300
03400
03500 SMOOTHING.
03600
03700 BUNDLING.
00100 ALPHABETIC SUMMARY OF CRE TELETYPE COMMANDS.
00200
00300
00400 "A" Toggle Arc Make flag.
00500 "B" Drive the cart backwards.
00600 "C" Cut intensity level.
00700
00800 "D" Toggle baby polygon delete flag.
00900 "E" Select Edge Display.
01000 "F" Drive the cart forwards.
01100
01200 "G"
01300 "H" Display histogram.
01400 "I" Input TV picture from a disk file.
01500
01600 "J" Contour TV image at levels 6% from ends of histogram.
01700 "K" Toggle Krakauer flag.
01800 "L" Set cart steering to hard left position.
01900 "αL" Pan cart camera to the left.
02000
02100 "M"
02200 "N" Next image.
02300 "O" Output TV file.
02400 "αO" Output CRE file.
02500 "P" Plot file output to disk the current III display buffer.
02600
02700 "Q" Contour TV image at equally spaced levels.
02800 "R" Set cart steering to hard right position.
02900 "αR" Pan cart camera to the right.
03000 "S" Select camera number.
03100
03200 "T" Take 4-bit television picture.
03300 "αT" Take 6-bit television picture.
03400 "U" Toggle KILVIC enable flag.
03500 "V" Enter cart diagnostic sub command mode.
03600
03700 "W" Alter Arc width table.
03800 "X" XGP output.
03900 "Y" Display arc-contour.
04000 "αY" Display both-contour.
04100 "βY" Display vector-contour.
04200 "εY" Display vector contour without dekinking.
04300
04400 "Z" Zero data structure.
04500 "αZ" Zoom Reset to initial display position.
00100 BASIC SET OF COMMANDS.
00200
00300 "T" Take a 4-bit television picture.
00400 "Q" Make CRE picture, from three intensity cuts.
00500 "αO" Output CRE file.
00600
00700 LINK FOLLOWING COMMANDS & NODE CONTENTS DISPLAY.
00800
00900 These 14 commands allow detailed inspection of the CRE data
01000 structure by showing the contents of a node. Data halfwords of a node
01100 are displayed as six octal digits; link halfwords are displayed prefixed
01200 with a letter indicating the type of node being pointed at; a zero
01300 link is displayed as "NIL".
01400
01500 The FILM node, which is the root of the whole data structure is fetched
01600 and displayed by the "+" command. From the Film, the ">" command can
01700 be used to get SON(FILM) which is always the first image, and ">" command
01800 of an image will get a level and ">" of a level will get a polygon.
01900 Now vectors, polygons, edges and faces are intensified when their contents
02000 are being displayed. The exit command is "!", which leaves the screen less
02100 cluttered.
02200
02300
02400
02500 "+" Fetch Film Node.
02600 "!" Flush diagonostic node display.
02700
02800
02900 WORD NODE FETCH
03000 POSITION COMMAND NAMES OF LINKS AT THIS WORD.
03100
03200 0. "," "." CW,,CCW
03300 1. "<" ">" DAD,,SON
03400 2. There is never a link at this word.
03500 3. "↓" "↑" NFACE,,PFACE or ENDO,,EXO
03600 4. "≤" "≥" NED,,PED or ARC,,PED
03700 5. "←" "→" NVT,,PVT or NGON,,PGON
03800 6. "⊂" "⊃" NTIME,,PTIME
00100 DISPLAY WINDOW SCROLLING COMMANDS.
00200
00300 ; MOVE CAMERA LEFT.
00400 : MOVE CAMERA RIGHT.
00500 ( MOVE CAMERA DOWN.
00600 ) MOVE CAMERA UP.
00700 - SHRINK IMAGE - ZOOM OUT.
00800 * MAGNIFY IMAGE - ZOOM IN.
00900 αZ RESET SCROLL VALUES.
01000 / HALVE STRENGTH OF SCROLLING DELTA.
01100 \ DOUBLE STRENGTH OF SCROLLING DELTA.
01200
01300 DISPLAY MODES.
01400
01500 "Y" DISPLAY ARC POLYGONS ONLY.
01600 "βY" DISPLAY VECTOR POLYGONS ONLY.
01700 (which usually do not exist unless the "U" command
01800 prevented their being deleted after being used.)
01900 "αY" DISPLAY BOTH ARC & VECTOR POLYGONS.
02000 "εY" DISPLAY VECTOR POLYGONS WITHOUT DEKINKING.
02100
02200 IMAGE OUTPUT COMMANDS.
02300
02400 "X" Output video image on Xerox Graphics Printer.
02500 "P" Output III plot file to disk.
00100 OPERATIONAL SUMMARY OF CRE TELETYPE COMMANDS.
00200
00300 INPUT/OUTPUT.
00400
00500 CART-CONTROL.
00600
00700 DISPLAY-CONTROL.
00800
00900 CONTOURING.
01000 "C" cut at level.
01100 "Q" equally spaced contours.
01200 "J" Make two contour with respect to per centage from
01300 ends of histogram.
01400
01500 "Q" - 3 CUTS: 20, 40, 60.
01600 "αQ" - 7 CUTS: 10, 20, 30, 40, 50, 60, 70.
01700 "βQ" - 8 CUTS: 04, 14, 24, 34, 44, 54, 64, 74.
01800 "εQ" - 15 CUTS: 04,10,14,20,24,30,34,40,44,50,54,60,64,70,74.
00100 CART CONTROL COMMANDS & OPERATING THE CART.
00200
00300 There are seven cart commands: drive forwards, drive
00400 backwards, turn left, turn right, pan camera left, pan camera right
00500 and halt:
00600
00700 "F" Drive Cart Forwards for one minute.
00800 "B" Drive Cart Backwards for one minute.
00900 "L" Turn steering wheels hard to left.
01000 "R" Turn steering wheels hard to right.
01100 "αL" Pan camera to the left for 10 seconds.
01200 "αR" Pan camera to the right for 10 seconds.
01300 " " Halt and continue spacewar job on PDP-6.
01400 "0" Halt and continue spacewar job on PDP-6.
01500 carriage return - Halt and stop spacewar job on PDP-6.
01600
01700
01800 First and most important is understanding how to stop the cart. The
01900 teletype halt command is " ", spacebar, or "0"; also any character
02000 other than "F", "B", "L", or "R" will stop the cart. Cart commands
02100 are passed first from a teletype to the PDP-10, then to the PDP-6,
02200 then over a citizens band, 27.045 megahertz, radio link to the cart
02300 control logic; and so when communications are lacking between
02400 entities in the chain of command the lower entities times out and
02500 causes the cart to halt. The cart control logic times out in a fifth
02600 of a second if it does not hear from the PDP-6; the PDP-6 times out
02700 in less than a minute if it has not heard from the PDP-10; the PDP-6
02800 also stops broadcasting cart commands if it detects the death of the
02900 PDP-10; the PDP-10 job times out after 5 minutes of not hearing
03000 from the teletype and kills the PDP-6 spacewar job.
03100
00100 II. FILE FORMATS.
00200 A. Television Image Format.
00300 B. Region/Edge Image Format.
00400
00500 A. Television Image Format.
00600
00700 The standard Cart's Eye television image is
00800 216 rows of 288 columns of 4 bits per pixel.
00900
01000 B. Contour/Region/Edge Image Format.
01100
01200 The image format, CRE, is essentially a core dump
01300 of CRE's internal node/link data structure. There are eight kinds
01400 of nodes and the nodes are fixed sized at six words per node.
01500
01600 From the top, the first node of a file is always a "FILM" node.
01700 The head of a film node points to a ring of "IMAGE" nodes.
01800 The head of an image node points to a ring of "LEVEL" nodes.
01900 The head of a level node points to a ring of "POLYGON" nodes.
02000 The head of a polygon node points to a ring of "EDGE" nodes.
02100 And edge nodes do not have a head pointer. Which is equivalent to
02200 saying that a file contains a film, a film is composed of images, an
02300 image is composed of levels, a level is composed of polygons and a
02400 polygon is composed of edges.
02500
02600 Now the detailed explanation will proceed bottom-up, starting
02700 with the most numerous edge nodes.
02800
02900 File names are accepted in the usual DEC format of name, dot,
03000 extension, left square bracket, project, comma, programmer, right
03100 square bracket, carriage return line feed. Where the filename is from
03200 one to six characters; and the extension project and programmer are
03300 from one to three characters. Everything but the filename is
03400 optional.
00100 IV. PERFORMANCE.
00200
00100 V. SAIL INTERFACING.
00200
00300 It should be possible to embed the CRE machine code under a
00400 SAIL core image; however I do not intend to do this work. For the
00500 present, the CRE interface to SAIL is only realized via a disk file
00600 transfer of the data structures. A CRE file may be read into an
00700 integer array in binary mode as illustrated below.
00800
00900 The first word of a CRE file is the first word of the film
01000 node which contains the size of the file in words. The film node has
01100 address 0; the next node has address 7; and so on in multiplies of
01200 seven. There are no empty nodes in a CRE file. The following SAIL
01300 program will read in a CRE file named X:
01400
01500 COMMENT EXAMPLE OF SAIL INPUT OF A CRE FILE;
01600 BEGIN "TEST"
01700 INTEGER SIZE;
01800 OPEN(1,"DSK",8,3,0,0,0,0);
01900 LOOKUP(1,"X.CRE",0);
02000 SIZE ← WORDIN(1);
02100 BEGIN
02200 INTEGER ARRAY NODE[0:SIZE];
02300 ARRYIN(1,NODE[1],SIZE-1);
02400 RELEASE(1);
02500 "MAIN PROGRAM.";
02600 END;
02700 END;
02800
02900 After the NODE array is loaded, CRE links and data may be accessed by
03000 their document names in a reasonible node-link notation using macros
03100 like the following:
03200
03300 DEFINE CW(Q) = "(NODE[Q] LSH -18)";
03400 DEFINE CCW(Q) = "(NODE[Q] LAND '777777)";
03500 DEFINE DAD(Q) = "(NODE[Q+1] LSH -18)";
03600 DEFINE SON(Q) = "(NODE[Q+1] LAND '777777)";
03700
03800 So that the first vertex of the first polygon of the first level of
03900 the first image of the film can be obtained:
04000
04100 INTEGER FILM,IMAGE,LEVEL,POLYGON,VERTEX;
04200
04300 FILM ← NODE[0];
04400 LEVEL ← SON(FILM);
04500 POLYGON ← SON(LEVEL);
04600 VERTEX ← SON(POLYGON);
04700
04800 The user may note that SAIL will compile three or more instructuions
04900 for what is known as a PDP-10 halfword operation; also if the user
05000 converts the CRE nodes and links into LEAP items and associations
05100 then an overhead of from ten to one hundred instructions per
05200 "halfword operation" will be incurred.
00100 VI. EDITORIAL REMARKS.
00200
00300
00400 1.
00500 The version of CRE discussed in this document is known to
00600 me as the third, or the version of Christmas-72. CRE-I of '68 and
00700 '69 was embedded in LISP and contained thresholding, bit raster
00800 operations, and a polygon trace routine. CRE-II was embedded in
00900 SAIL, and in early forms even used LEAP. Both CRE-I and CRE-II
01000 were built around the notion of "windowing". CRE-IV, of
01100 Thanksgiving-72 was was scan line oriented.
01200
01300
01400 3.
01500 It is my impression that all the so called "scientific" ideas
01600 in CRE have appeared elsewhere. In particular, I was aware of and
01700 kind of liked the work of Krakauer, Zahn, and Mc Cormick's
01800 ILLAIC-III. Also, I was aware of and disliked the work of Pingle and
01900 Hueckel. I wish to acknowledge all these people from whom I have
02000 borrowed ideas, both positive and negative. On the other hand, I
02100 alone wrote and developed all the code in CRE.
02200
02300 4.
02400 Future CRE feature might include, a window version, image
02500 comparison, and MAKVID.
02600
02700 5. Prejudiced and Unprejudiced Vision.
02800
02900 6. ANTI VARIABLE WINDOWING.
03000
03100 The requirement that a vision program must handle variable
03200 sized windows is a very severe limitation which I believe has bogged
03300 down many potentially good image processing ideas in a morass of word
03400 packing, array binding, window splicing, and cost optimization; all
03500 of which matters are not directly relevant to image processing.
03600
03700 7. ANTI VISUAL FEEDBACK ON THE TACTICAL LEVEL.
03800
03900 It has become a banal truism in computer vision reseach that
04000 a vision system must have feedback, accomodation, prediction,
04100 verification, and higher level knowledge. The pursuit of this visual
04200 feedback format seems to lead one to work solely on building a forest
04300 without worrying about how to build a tree.
04400
04500 8. ANTI HIGHER LEVEL LANGUAGES & PRO MACHINE CODE.
04600
04700 It has become a banal truism that a higher level language
04800 allows rapid implementation and experimental change of poorly understood
04900 algorithms.
00100 CODE DOCUMENTATION.
00200
00300 The CRE code uses additional PDP-10 mnemonics for the sake of
00400 pronouciation and brevity. The mnemonics stem from ancient PDP-1
00500 nomenclature; in the PDP-10 the left half word is the instruction
00600 part and the right half word is the address part. The codes CAR and
00700 CDR are traditional LISP names, derived from IBM-709 nomenclature;
00800 CAR and CDR are appropriate PDP-6/10 op codes because according to
00900 Kotok,the machine was designed to facilitate LISP.
01000
01100 HLR LIP Load Instruction Part.
01200 HRR LAP Load Address Part.
01300 HRLM DIP Deposit in Instruction Part.
01400 HRRM DAP Deposit in Instruction Part.
01500
01600 HRRZS ZIP Zero Instruction Part.
01700 HLLZS ZAP Zero Address Part.
01800 HRROS WIP W'ones to Instruction Part.
01900 HLLOS WAP W'ones to Address Part.
02000
02100 HLRZ CAR Contents Address Register.
02200 HRLI LIPI Load Instruction Part Immediate.
02300 HRRI LAPI Load Address Part Immediate.
02400 HRLZM DIPZ Deposit into Instruction Part with Zeroes.
02500
02600 HRRZ CDR Contents Decrement Register.
02700 MOVEI LACI Load Accumulator Immediate.
02800 MOVSI SLACI Swap Load Accumulator Immediate.
02900 HRRZM DAPZ Deposit into Address Part with Zeroes.
03000
03100 MOVE LAC Load Accumulator.
03200 MOVN LACN Load Accumulator Negative.
03300 MOVM LACM Load Accumulator Magnitude.
03400 MOVS SLAC Swap Load Accumulator.
03500
03600 MOVEM DAC Deposit Accumulator into memory.
03700 MOVNM DACN Deposit Accumulator Negative.
03800 MOVMM DACM Deposit Accumulator Magnitude.
03900 MOVSM SDAC Swap Deposit Accumulator.
04000
04100 HLRE NIP Number from Instruction Part.
04200 HRRE NAP Number from Address Part.
04300 HRREI NIM Number Immediate.
04400 JRST GO Load program counter immediate.
00100 REFERENCES.
00200
00300 KNUTH
00400 KRAKAUER
00500 GEOMED SAILON
00600 WINGED EDGE PAPER